#include <iostream>
#include <queue>
using namespace std;

struct HeapNode
{
    int row; //行
    int col; //列
};

struct cmp
{
    // 自定义比较函数，在优先队列中将会用到，优先级的设定
    bool operator()(HeapNode a, HeapNode b)
    {
        if (a.row == b.row)
            return a.col > b.col; // 同一行的列号越小优先级越高
        return a.row < b.row;     // 不同行行号行号越大优先级越高
    }
};

// priority_queue为优先队列类模板,根据优先级（cmp）进行排列
void AddLiveNode(priority_queue<HeapNode, vector<HeapNode>, cmp> &maximum_heap, int i, int n)
{
    HeapNode node;
    for (int j = 1; j <= n; j++)
    {
        node.row = i;
        node.col = j;
        maximum_heap.push(node);
    }
}

bool place(int k, int *track)
{
    for (int j = 1; j < k; j++)
        if ((abs(k - j) == abs(track[j] - track[k]) || (track[j] == track[k]))) //前面的是检查是否在同一对角线上后面是是否在同一列上  
            return false;
    return true;
}

bool nqueens(priority_queue<HeapNode, vector<HeapNode>, cmp> &maximum_heap, int n, int *track)
{
    AddLiveNode(maximum_heap, 1, n);
    int i = 0;
    do
    {
        i = maximum_heap.top().row;
        /*防止超过界限赋值，以避免指针越界。*/
        if (i != n + 1)
            track[i] = maximum_heap.top().col; //取队首元素
        maximum_heap.pop();                    //队首元素出队
        /*防止超过界限，以避免指针越界。*/
        if (i != n + 1)
        {
            if (place(i, track))
                AddLiveNode(maximum_heap, i + 1, n);
        }
        if (maximum_heap.empty())
            return false;
    } while (i != n + 1);

    while (!maximum_heap.empty())
        maximum_heap.pop();

    return true;
}

int main()
{
    int track[5]{0};
    priority_queue<HeapNode, vector<HeapNode>, cmp> Q;
    nqueens(Q, 4, track);
    for (int i = 0; i < 5; i++)
        cout << track[i] << " ";
    cout << endl;
    return 0;
}

/*
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
*/